Night Owl 9/Night Owl CD-ROM (NOPV9) (Night Owl Publisher) (1993).ISO/015a/dea001.zip/DEA.DOC

Text File | 1993-04-13 | 15KB | 317 lines

                         The Data Encryption Algorithm
                                  DEA V. 1.00
                      Public Shareware Evaluation Release
                                 Documentation
                         Copyright 1993 by V. Sadowsky
------------------------------------------------------------------------------


HISTORICAL OVERVIEW

     The DEA encryption algorithm was designed over the course of 14 months.  It
has its roots in Number Theory.  In particular, I had observed some peculiar and
interesting features of PERIODIC DECIMALS.  The DEA is the result of my desire
to create an encryption algorithm based on this property of fractions with a
prime divisor.  This should not be surprising because there exist numerous
examples in the literature of encryption algorithms based on the mathematical
properties of various equations.  Some noteworthy examples are: the RSA,
discrete exponentiation, and the Knapsack problem (solved).

     I had been looking around for some time for a method of generating the
elusive ONE-TIME-PAD.  That, is, a random bit stream.  But the problem was that
most computer generated numbers were in fact not random, but PSEUDOrandom.  I
knew that reliance on pseudorandomness was wasted effort.  How then could I
generate a random bitstream based on a mathematically precise algorithm?

     The answer lay in a BYTE Magazine article I had read some years earlier
where the authors made the point that ALL decimal expansions of rational
fractions repeat themselves in a cyclical manner.  They had developed a program
to compute the decimal period, as it is known.  I was later to discover that one
of their cited examples was a composite number (their divisor) and thus had a
relatively short cycle of repetition.  However, because they did not have all
the facts of the matter, they proclaimed that they had not found the divisor
99,993 to repeat in their tests.  They knew that it must eventually repeat, but
I suppose they had no idea of whether its length was less than, or more than
99,993.  The decimal period of this divisor, is, of course, much less than
99,993.  However, herein lay the germ of the idea to employ fractions in the
production of the ONE-TIME-PAD random bit-stream for a cryptographic algorithm.

     The DEA uses the one-time-pad technique outlined above, but it also goes
several steps beyond.  First, the DEA generates what I shall call, for lack of a
better term, Sadowsky Fractions.  A Sadowsky Fraction is a series of unrelated
fractions starting with a Defined Fraction such as 117 / 22,307.  Now, the prime
divisor 22,307 has a decimal period of 11,153 quotient digits.  If, during the
long division of 117 by 22,307 we add the quotient digit to BOTH the numerator
AND the residue, then we will be producing Sadowsky Fractions.  Let's look at
this more mathematically:
                          Let the quotient digits 225806451...continued
                          represent the REAL decimal period of the rational
                          fraction 7 / 31.
Now, let's simply define a new fraction 5,307 / 22,307 (EQU. ->0.237907383...
And now, Sadowsky Fractions will produce:

    53070 / 22307  Q = 2   residue = 8456
                                          8456 + 2 = 8458
                                          8458 * 10 = 84580
   84580 / 22309   Q = 3   residue = 17653
                                           17653 + 2 = 17655
                                           17655 * 10 = 176550
   176550 / 22311   Q = 7  residue = 20373
                                           20373 + 5 = 20378
                                           20378 * 10 = 203780
   203780 / 22316   Q = 9  residue = 2936
                                           2936 + 8 = 2944
                                           2944 * 10 = 29440
   29440 / 22324    Q = 1  residue = 7116
                                           etc.
                                           etc.
   etc.

Observe how the original REAL decimal period of 237907383 is now permuted into:
                                                23791.... etc.

Our new decimal period no longer corresponds to one modulus, but to five (5), in
our limited example.  Thus Sadowsky Fractions are fractions wherein the long
division process both the residue and the modulus are affected by addition of
'random quotient noise' from another real, or imaginary decimal period.  We may
think of the above example 23791... as the 'imaginary' decimal period.  In one
stroke, we have a method for producing a one-time-pad, AND a precise
mathematical permutation.  The exact degree of permutation depends on the
fractions used and the decimal periods.  In the example, differentation occurrs
only after five division steps.  This length varies, and thereafter, the
differentation becomes very pronounced.  The length of a Sadowsky decimal period
is dependent upon the length of the 'feed' digits.  If we have 11,153 digits of
PI, or square root 2, or some other source of quotients, we may use that as a
feed to a defined fraction, which will in turn, spawn that many Sadowsky
Fractions.  Secondly, the DEA employs ten (10) defined fractions intended to
spawn as many Sadowsky Fractions as necessary to process one of ten input file
blocks.




 MOTIVATION FOR CREATING THE DATA ENCRYPTION ALGORITHM


     The motivation for this project was based on five factors as follows:

o  my desire to create an encryption algorithm based within the framework of
   periodic decimals

o  the fact that the industry's Data Encryption Standard algorithm (DES)
   was found in numerous software packages and the fact that DES, while it
   is a brilliant achievment!!, is now outdated and the subject of attainable
   brute-force key attacks

o  many software encryption methods not using the DES, were based on very
   simple ideas, such as, using a simple secret alphanumeric key.  Some were
   so rudimentary that they should not take space on a floppy disk!!

o  my need to be different and design an algorithm which would withstand both
   exhaustive key and ciphertext attacks

o  need to to be creative and perhaps, enrich and infuse some creativity into
   the literature and maybe, show how the one-time-pad technique may be
   implemented



DIFFERENCES AND FEATURES WITH REGARD TO OTHER ENCRYPTION ALGORITHMS


     The major differences between the DEA and other systems is outlined below:

o  uses the one-time-pad method
o  uses a 240-byte key containing 20 fractions along with quotient select
   digit info. and byte XOR number
o  uses only bit XOR manipulations to produce the cipher byte
o  there is no brute-force method of extracting the user's key(s)
o  the original message (in-file) is not expanded in any manner
o  keys are not stored within the ciphertext
o  encryption and decryption accomplished in one code section, not two



THE DEA KEY STRUCTURE


     The DEA key structure is totally different from any other system in that it
uses fractions, 20 of them, along with other information (as noted above).  This
makes them both impossible to determine if unauthorized, but also difficult, if
not impossible to memorize.  They are also somewhat tedious to create.

     Fortunately, DEA keys may be saved to a disk file and retrieved at any
later date when it is desired to use that same key again.

     One important feature of the DEA key design is that the DEA key is designed
to be used frequently.  The design of the key makes it a 100 per cent fruitless
expenditure of effort in attacking the DEA key itself.  It is NOT subject to
brute-force attacks, as with many encryption systems, regardless of complexity,
that employ one or more alphanumeric keys.  Note that using the same key
frequently and for a long time, is breaking a golden rule in cryptography.
However, it does not concern the DEA user.

     Since the DEA divides the input file into ten blocks, there are ten DEA
keys.  Each key contains a fraction to generate a REAL decimal period, and a
defined fraction designed to generate a series of Sadowsky Fractions.  The very
most that one could possibly decipher without all ten keys (assume one DEA key
is correct), is ONE BYTE, AND THIS IS ONLY POSSIBLE (IF) THE ASSUMED KEY IS
INDEED THE FIRST DEA KEY.  This is because ALL DEA keys are very heavily
integrated with oneanother.

     The only real hassle with DEA keys is inputting all the required numbers.
Once this is done, all DEA keys are saved.  Using the DEA with say, 10 or more
keys on file, makes the DEA very user friendly, and easier to use than most file
encryption programs I have tested.

     The XOR number is a critical component of the DEA key.  This value
specifies how many bit XOR are to be performed.  This value should be larger
than 15 and less than 50.  The larger the better, since larger values will
involve much more bit manipulation.



DEA DO'S AND DONT'S


     This section will outline several aspects of using the DEA software
program.

     DON'T
--------------
  o  Enter ALL mandatory information as requested by the program, especially
     if entering a new DEA key

  o  NEVER (!!!) enter a numerator greater than the divisor.  All numerators
     MUST BE SMALLER THAN DIVISORS

  o  Don't enter the same set of numbers, either numerators, divisors, or
     prime divisors

  o  Do not enter the name "DEA.OUT" as a filename for DEA to process.  Since
     "DEA.OUT" will also be the output filename, this conflict will result in
     MS-DOS (R) file errors and errenous decryption!!

  o  DON'T lose your DEA.KEY file, it contains YOUR secrets!!  REMEMBER, DEA
     keys are a pain to set-up, so don't mess with this file!!!  The file
     grows in multiples of 240 bytes with the addition of new keys.


     DO
--------------
  o  the output filename of the DEA program is named "DEA.OUT", ALWAYS RENAME
     this file ONLY IF IT IS A DEA ENCRYPTED FILE.  You do not need to rename
     the file if it is decrypted.  If it's encrypted, it is assumed that some
     time later, you will want to decrypt it, at that time, its name MUST be
     something OTHER THAN "DEA.OUT".

  o  make a habit a introducing 'distance' between the numbers you enter as
     fractions.  For example, for key 1 you could enter a small prime divisor
     and then a large denominator for the defined fraction.  Experiment a bit!

  o  if you have several DEA keys on file, you will have to remember which
     DEA key was used with a particular file.  Otherwise you would have to
     try all of them until one of them produced a readable or runable output.

  o  As with any encryption algorithm, compression and encryption are related
     in that both deal with entropy, compression attempts to decrease the
     entropy (redundancy), and encryption is designed to increase the entropy
     (the randomness, disorder).
     You can save time and space by, for example, compressing all source
     files into an archive, THEN encrypting them.  When you want to get your
     files back, you must decrypt FIRST, then use your favourite compression
     program.  Make sure you change the file name of DEA.OUT to say, DEA.ARJ,
     or DEA.LZH, or DEA.ZIP.
     Compression is convenient and logical for some business environments.



THE DEA OUTPUT FILES


     The DEA program will open several files IN THE DEFAULT DIRECTORY.  These
files are:

           DEA.OUT       * standard DEA output file
           DEA.KEY       * DEA key file   **** TAKE GOOD CARE OF THIS ****
           DEA.Q1        * first quotient file   850 bytes
           DEA.Q2        * second quotient file  850 bytes
           DEA.PIF       * DEA program info. file   -dbg.- version
           DEA.ADR       * DEA random addresses     -dbg.- version

The last two files are only produced by the DEA debug version.  This version of
the DEA program runs more slowly than the non-debug version because it has two
more files to write.  Further, these two files, can become quite LARGE!!

Unless you are testing the DEA cryptographically, it is recommended that only
the non-debug version be used as it is much faster.



DEA ENCRYPTION AND DECRYPTION


     The DEA does not use the traditional -e / -d flags, instead, the DEA goes
its merry way using the specified key and either encrypts or decrypts the
indicated file.  The user must know what he / she is doing with a file.  Thus,
if the file is encrypted, running it through the DEA with the SAME key, will
decrypt it.



FURTHER NOTES


     The DEA never uses the same pieces of key information twice.  Every input
byte generates a unique one-time-pad of 850 digits.

     The DEA is not a self-synchronizing cipher; if bits are altered in a DEA
encrypted file, then upon decryption, only those bytes will be errenous.

     The DEA is a stream cipher.



DEA SECURITY


     The most unique aspect of the DEA is its key structure, and this structure
naturally emerged from the design framework.  The security of the DEA is,
therefore, solid from the key perspective.  However, from the ciphertext
perspective, this solidity may be less than 100%.  The best and most effective
test of a cipher is  t i m e.  However, this document was written to provide an
overview and provide general guidelines for using the software correctly so that
it could, hopefully, be given a fair trial run to determine its strengths and
weaknesses.

     Please understand that I am not a professional cryptographer, just a fellow
with a long interest in data encryption techniques.  This is why I am not
qualified to determine fully the security of the DEA design.



PURPOSE OF PUBLIC SHAREWARE EVALUATION RELEASE


     The purpose of releasing this software is mainly for testing; I am hoping
that it will be widely distributed and will come into the hands of people
qualified in the field of cryptography who will undertake to study the DEA
design further, and hopefully report back to me.

     While this document does not cover all aspects of the DEA design, it is a
general overview; I will attempt to answer all correspondences.

     I encourage your distribution of this software and welcome all questions
and comments regarding the DEA and its design innards.

                      send comments, money, questions to:

                                  V. Sadowsky
                                  33 Isabella St. Ste. 1005
                                  Toronto, Ontario
                                  M4Y 2P7
                                  Canada

------------------------------ End DEA.DOC -----------------------------------